The Celebrity Problem

       
    
    A celebrity is a person who is known to all but does not know anyone at a party. If you go to a party of
    N people, find if there is a celebrity in the party or not.
    A square NxN matrix M[][] is used to represent people at the party such that if an element of row i
    and column j  is set to 1 it means ith person knows jth person. Here M[i][i] will always be 0.
    Note: Follow 0 based indexing.
    
    Example 1:

    Input:
    N = 3
    M[][] = {{0 1 0},
         {0 0 0}, 
         {0 1 0}}
    Output: 1
    Explanation: 0th and 2nd person both know 1. Therefore, 1 is the celebrity. 

    Example 2:

    Input:
    N = 2
    M[][] = {{0 1},{1 0}}
    Output: -1
    Explanation: The two people at the party both know each other. None of them is a celebrity. 
 
      
      
      

        
        

        Code

#define MAX 501

int getId(int M[MAX][MAX], int n)
{
    stack<int>s;
    int i,j;
    for(i=0;i<n;i++)
    {
        s.push(i);
    }
    while(s.size()>=2)
    {
         int j;
         i=s.top();
         s.pop();
         j=s.top();
         s.pop();
         if(M[i][j]==1)
          s.push(j);
         else 
           s.push(i);
           
    }
    int cel=s.top();
    s.pop();
    for(i=0;i<n;i++)
    {
        if(i!=cel)
        {
            if(M[i][cel]==0||M[cel][i]==1)
             {
                 return -1;
             }
        }
    }
    return cel;
    
}